$Description$
$Solution$
分开计算每条边的贡献。
边对点产生贡献,当且仅当边的两端都有点。
于是对于$(u,fa)$,$u$的子树选中了$x$个点,我们可以分开计算白点和黑点的贡献$sum:$
$sum_{(u,fa)}=x(k-x)+(size[u]-x)(n-size[u]-k+x)$
$dp[fa][x]=dp[fa][x-y]+dp[v][y]+sum{(u,fa)}w{(u,fa)}$
把$u$打成$y$水过两个点$QWQ$
1 |
|
Viva la Vida
分开计算每条边的贡献。
边对点产生贡献,当且仅当边的两端都有点。
于是对于$(u,fa)$,$u$的子树选中了$x$个点,我们可以分开计算白点和黑点的贡献$sum:$
$sum_{(u,fa)}=x(k-x)+(size[u]-x)(n-size[u]-k+x)$
$dp[fa][x]=dp[fa][x-y]+dp[v][y]+sum{(u,fa)}w{(u,fa)}$
把$u$打成$y$水过两个点$QWQ$
1 | #include<cstdio> |